#include <cstdlib>
#include <vector>
#include <string>
#include <iostream>
#include <fstream>
#include <list>
#include <limits.h>
#include <limits>
#include <ctime>
#include <omp.h>

using namespace std;


vector<vector<long> > readFile(string filePath);
vector<long> dijkstra(int source, vector<vector<long> > &distanceMatrix);
vector<long> slflll(int source, vector<vector<long> > &distanceMatrix);
bool compareVectors(vector<long> &v1, vector<long> &v2);
inline double calculateAvarage(list<int> &q, vector<long> &dist);
bool contain(list<int> &q, int v);
int shortestQueue(vector<list<int> > &queues);

void process(char* fileName);

int main(int argc, char** argv) {
    //test read file function
    process("../netflow10.txt");

//    process("../netflow50.txt");
//
//    process("../netflow500.txt");
//
//    process("../netflow1000.txt");

    return 0;
}

vector<long> dijkstra(int source, vector<vector<long> > &distanceMatrix)
{
    int edges = distanceMatrix.size();
    vector<long> dist(edges);
    bool visited[edges];
    int i, j, u;
    long alt, min;
    for(i=0; i<edges; i++)
    {
        visited[i] = false;
        dist[i] = distanceMatrix[source][i];
    }
    visited[source] = true;

    for(j=1; j<edges; j++)
    {
        min = numeric_limits<long>::max();
        for(i=0; i<edges; i++)
        {
            if(dist[i] < min && !visited[i])
            {
                min = dist[i];
                u = i;
            }
        }
        visited[u] = true;
        for(i=0; i<edges; i++)
        {
            alt = dist[u] + distanceMatrix[u][i];
            if(alt < dist[i])
            {
                dist[i] = alt;
            }
        }
    }

//    for(i=0;i<edges;i++)
//    {
//        cout<<"DIJKSTRA Najkrotsza sciezka z "<< source << " do " <<i<<" to: "<<dist[i]<<"\n";
//    }

    return dist;
}


//zamiast jednej kolejki mozna wrzucic kilka i wtedy zrównoleglić
vector<long> slflll(int source, vector<vector<long> > &distanceMatrix){
    int edges = distanceMatrix.size();
    vector<long> dist(edges);
    bool inQueue[edges];

//    list<int> queue;
//    int liczba_kolejek = 4;
    vector<list<int> > queues(4);

    //set distance to inf
    for(int i=0; i<edges; i++){
        if(i != source){
            dist[i] = std::numeric_limits<long>::max();
        }else{
            dist[i] = 0;
        }
        inQueue[i] = false;
    }

    queues[0].push_front(source);
    inQueue[source] = true;
//    queue.push_front(source);

    //tutaj jakieś przypisanie kolejek do procesorow

    while(!(queues[0].empty() && queues[1].empty() && queues[2].empty() && queues[3].empty())){
        #pragma omp parallel num_threads (4)
        {
             while(!(queues[omp_get_thread_num()].empty())){
                int id = omp_get_thread_num();
//                cout << "Watek nr: " << id << endl;
                //lll
                double c = calculateAvarage(queues[id], dist);
                int i = queues[id].front();
//                cout << "C: " << c << endl;
//                cout << "i: " << i << endl;
                while(dist[i] > c){
                    queues[id].pop_front();
                    queues[id].push_back(i);
                    i = queues[id].front();
                }

                inQueue[i] = false;
                queues[id].pop_front();
//                cout << "i: " << i << endl;

                for(int j=0; j<edges; j++){
                    if(j != i){
                        if(dist[i] + distanceMatrix[i][j] < dist[j]){
                            dist[j] = dist[i] + distanceMatrix[i][j];
                            #pragma omp critical
                            {
                                int q = shortestQueue(queues);
                                //check if v is in any queue
                                //slf
                                if(!inQueue[j]){
                                    if(queues[q].empty() || dist[j] < dist[i]){
                                        queues[q].push_front(j);
                                    }else{
                                        queues[q].push_back(j);
                                    }
                                    inQueue[j] = true;
                                }
                            }
                        }
                    }
                }
//                cout << "Kolejka: " << queues[id].size() << endl;
            }
        }
    }
//    for(int i=0;i<edges;i++)
//    {
//        cout<<"SLF-LL Najkrotsza sciezka z "<< source << " do " <<i<<" to: "<<dist[i]<<"\n";
//    }

    return dist;
}

vector<vector<long> > readFile(string filePath){
    vector<vector<long> > distanceMatrix;
    string line;

    int edges;

    ifstream myfile(filePath.c_str());
    if (myfile.is_open()){
        myfile >> edges;

        distanceMatrix.resize(edges);

        for(int i=0; i<edges; i++){
            distanceMatrix[i].resize(edges);

            for(int j=0; j<edges; j++){
               myfile >> distanceMatrix[i][j];
            }
        }
    }
    return distanceMatrix;
}

bool contain(list<int> &q, int v){
    if(q.empty()){
        return false;
    }
    for (std::list<int>::iterator it=q.begin(); it != q.end(); ++it){
        if(*it == v){
            return true;
        }
    }
    return false;
}

inline double calculateAvarage(list<int> &q, vector<long> &dist){
    double result = 0;
    for (std::list<int>::iterator it=q.begin(); it != q.end(); ++it){
        result += dist[*it];
    }

    if(q.size() != 0){
        result /= q.size();
    }
    return result;
}

bool compareVectors(vector<long> &v1, vector<long> &v2){
    if(v1.size() != v2.size()){
        return false;
    }

    for(int i=0; i<v1.size(); i++){
        if(v1[i] != v2[i]){
            return false;
        }
    }

    return true;
}

void process(char* fileName){
    vector<vector<long> > distanceMatrix = readFile(fileName);

    int edges = distanceMatrix.size();

    //obliczenia metodą dijkstry
    vector<vector<long> > distDijkstra(edges);
    for(int i=0; i<edges; i++){
        distDijkstra[i].resize(edges);
    }
    clock_t cl = clock();
    for(int i=0; i<edges; i++){
        distDijkstra[i] = dijkstra(i, distanceMatrix);
    }
    cl = clock() - cl;

    cout << "Dla " << edges << " wierzcholkow obliczenie sciezek metoda Dijkstry zajelo: " << ((float)cl)/CLOCKS_PER_SEC << endl;

    //obliczenia metodą SLF-LLL
    vector<vector<long> > distSLFLLL(edges);
    for(int i=0; i<edges; i++){
        distSLFLLL[i].resize(edges);
    }
    cl = clock();
    for(int i=0; i<edges; i++){
        distSLFLLL[i] = slflll(i, distanceMatrix);
    }
    cl = clock() - cl;

    cout << "Dla " << edges << " wierzcholkow obliczenie sciezek metoda LSF-LLL zajelo: " << ((float)cl)/CLOCKS_PER_SEC << endl;

    bool same = true;
    //porównanie otrzymanych wyników
    for(int i=0; i<edges; i++){
        if(!compareVectors(distDijkstra[i], distSLFLLL[i])){
            same = false;
            break;
        }
    }

    cout << "Otrzymane wyniki sa takie same? " << same << endl;
}

int shortestQueue(vector<list<int> > &queues){
    int resultSize = queues[0].size();
    int result = 0;
    for(int i=1; i<queues.size(); i++){
        if(queues[i].size() < resultSize){
            result = i;
        }
    }

    return result;
}
